The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Robotic networks are progressively used more and more in industrial and scientific applications. Robotic networks attract researchers' attention, because of their ability to incorporate multiple technological platforms, including computational, sensing, communications and movement platforms. Additionally, such networks are suitable to be used in a wide range of applications where human intervention is limited or denied. Such applications include, for example, rescue operations, surveillance, logistic and humanitarian demining, as well as applications where there are economic benefits for using mobile robots such as farming or production line applications. Advantages of using robotic networks include flexibility of modifying the robotics network to match different application scenarios, robustness of multi-robot system against failure and parallelism operation, which leads to a time efficient system.
A team of robots is able to map an area and identify unsafe areas. The team can locate tasks either by itself if the robots are equipped with appropriate sensors or with the help of an external system, such as a wireless sensor network (WSN). The task could be carrying goods in a warehouse application, cleaning in a cleaning operation scenario, or finding victims in a surveillance application. In many scenarios, task locations and requirements are not known beforehand because they emerge as needed in the area. Hence, an offline task assignment approach is not a feasible solution. Therefore, an on-line distributed task allocation approach is needed for such dynamic scenarios.
The problem of assigning a set of tasks to a set of robots to optimize certain metrics is called multi-robot task allocation (MRTA), and it is considered to be one of the main challenges in multi-robot systems (MRS). Furthermore, it is more challenging if tasks must be assigned in a distributed manner as they appear in real-time.
There are different MRTA approaches which can be classified into three major categories: centralized approaches, market-based approaches, and behavior-based approaches. Centralized approaches are suitable for a small number of robots in a static environment. They suffer from a single point of failure and high communication overhead, and they respond slowly to local changes. In contrast, fully distributed approaches, such as behavior-based approaches are robust to failures, flexible, and require less computational and communication resources; however, they work on local optimal solutions, which do not necessarily aggregate to produce the globally optimal solution, and thus, they yield suboptimal solutions.
The market-based/auction-based approach, one of the most popular algorithms of MRTA, is considered to be the mid-point between fully centralized and fully distributed approaches. It works in a similar manner as an auction process in the market, where an auctioneer opens an auction and then bidders submit their offers, with the auctioneer granting the item to the highest bidder. In the market-based approach, the bid is computed by each robot as a function of its utility in performing a task. There are primarily two common types of auctions: single-task auctions and combinatorial auctions. In a single-task auction, there is one task, and it is granted to the highest bidder. In a combinatorial auction, multiple tasks are offered in one auction, and bidders can bid on any subset of the offered tasks based on the robots' decision.
The problem of the single-task approach is that it does not consider the synergy among tasks, which leads to a suboptimal solution. Synergy is a term used to describe the relationship between tasks; tasks have positive synergy if the total cost of executing them by one robot is less than the total cost if they are executed by more than one robot. In contrast, because the combinatorial auction allows robots to bid on a subset of tasks, robots can bid on tasks that have positive synergy, and thus, it produces a better solution. However, the combinatorial auction requires high computational resources because the number of possible bundles increases exponentially with the number of tasks. Sequential single-item (SSI) auctions are an alternative to combinatorial auctions. In SSI auctions, robots bid on all unallocated tasks by the minimum cost increase in the sum of the minimum path to visit the assigned tasks. The robot with the smallest bid wins a task, and then, the bidding process begins again for the remaining unallocated tasks. After all tasks are allocated, robots compute the minimum path to their tasks and move accordingly.
Accordingly, there is a need for an online distributed multi-objective task allocation system (DYMO Action) that assigns the tasks emerging scenario which provides immunity against single point failures, utilizes low processing/computational costs, and performs local and global optimal solutions that takes into consideration task synergy and quality considerations for tasks and performing robots.